/*
 * @lc app=leetcode.cn id=221 lang=golang
 *
 * [221] 最大正方形
 */

// @lc code=start
func maximalSquare(matrix [][]byte) int {
	ans := conv(matrix[0][0])
	if len(matrix) == 1 {
		for i := 0; i < len(matrix[0]); i++ {
			ans = max(ans, conv(matrix[0][i]))
		}
		return ans
	}

	if len(matrix[0]) == 1 {
		for i := 0; i < len(matrix); i++ {
			ans = max(ans, conv(matrix[i][0]))
		}
		return ans
	}

	dp := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		dp[i][0] = conv(matrix[i][0])
	}

	for i := 0; i < len(matrix[0]); i++ {
		dp[0][i] = conv(matrix[0][i])
	}

	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			if conv(matrix[i][j]) == 0 {
				dp[i][j] = 0
				ans = max(dp[i][j-1], max(dp[i-1][j], max(dp[i-1][j-1], ans)))
			} else {
				dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + conv(matrix[i][j])
				ans = max(dp[i][j-1], max(dp[i-1][j], max(dp[i-1][j-1], max(ans, dp[i][j]))))
			}
		}
	}

	return ans * ans
}

func conv(b byte) int {
	if b == '1' {
		return 1
	}
	return 0
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

